import java.util.*;

public class Solution {

    public String mostCommonWord(String paragraph, String[] banned) {
        paragraph = paragraph.toLowerCase();
        Map<String,Integer> hashMap = new HashMap<>();
        Set<String> set = new HashSet<>();
        for (String s1 : banned) {
            set.add(s1);
        }
        String s = "";
        for (int i = 0; i < paragraph.length(); i++) {
            char ch1 = paragraph.charAt(i);
            if (Character.isLetter(ch1)) {
                s = s+ch1;
            }else {
                if (!set.contains(s)) {
                    if (!s.isEmpty() && hashMap.get(s) == null) {
                        hashMap.put(s, 1);
                    } else {
                        if (!s.isEmpty()) {
                            hashMap.put(s, hashMap.get(s) + 1);
                        }
                    }
                    s = "";
                }
                s ="";
            }
        }
        String ret = s;
        int max = 0;
        for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {
            if (entry.getValue() > max ) {
                ret = entry.getKey().toString();
                max = entry.getValue();
            }
        }
        return ret;
    }

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] num1 = new int[words.length];
        for(int i=0;i < words.length;i++) {
            num1[i] = func(words[i]);
        }
        Arrays.sort(num1);
        int[] num2 = new int[queries.length];
        for(int i=0;i < queries.length;i++) {
            int x = func(queries[i]);
            int left = 0;
            int right = words.length;
            while(left < right) {
                int mid = (left+right)/2;
                if(num1[mid] > x) {
                    right = mid;
                }else {
                    left = mid+1;
                }
            }
            num2[i] = words.length - left;
        }
        return num2;
    }
    public int func(String word) {
        int[] array = new int[26];
        for(int i =0;i < word.length();i++) {
            char ch = word.charAt(i);
            array[ch-'a']++;
        }
        for(int x : array) {
            if(x > 0) {
                return x;
            }
        }
        return -1;
    }

    public int lengthOfLongestSubstring(String s) {
        Character[] s1= new Character[s.length()];
        for (int i = 0; i < s.length(); i++) {
            char ch =s.charAt(i);
            s1[i] = ch;
        }
        Set<Character> set = new HashSet();
        int left = 0;
        int right = 0;
        int length = 0;
        int maxlength = 0;
        int i = 0;
        while(right < s1.length) {
            if(!set.contains(s1[right])) {
                set.add(s1[right]);
                length++;
                if(length > maxlength) {
                    maxlength = length;
                }
                right++;
            }else {
                while (set.contains(s1[right])) {
                    set.remove(s1[left]);
                    left++;
                    length--;
                }
                set.add(s1[right]);
                right++;
                length++;
            }
        }
        return maxlength;
    }

}
